home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph / _planar_map.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  6.4 KB  |  335 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _planar_map.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/planar_map.h>
  17.  
  18. extern bool PLANAR(graph&, bool=false);
  19.  
  20. list<edge> planar_map::adj_edges(face f) const
  21. { list<edge> result(f->head);
  22.   edge e1 = succ_face_edge(f->head);
  23.   while (e1!=f->head)
  24.   { result.append(e1);
  25.     e1 = succ_face_edge(e1);
  26.    }
  27.   return result;
  28.  }
  29.  
  30. list<node> planar_map::adj_nodes(face f) const
  31. { list<node> result(source(f->head));
  32.   edge e1 = succ_face_edge(f->head);
  33.   while (e1!=f->head)
  34.   { result.append(source(e1));
  35.     e1 = succ_face_edge(e1);
  36.    }
  37.   return result;
  38.  }
  39.  
  40. list<face> planar_map::adj_faces(node v) const
  41. { list<face> result;
  42.   edge e;
  43.   forall_out_edges(e,v) result.append(adj_face(e));
  44.   return result;
  45.  }
  46.  
  47. face  planar_map::new_face(GenPtr i) 
  48. { 
  49.   face f=new i_face(i,this);
  50.   f->loc=F_list.append(f);
  51.   return f;
  52.  }
  53.  
  54.  
  55. edge planar_map::split_edge(edge e, GenPtr node_inf)
  56. { 
  57.   /* splits edge e and its reversal by inserting a new node u (node_inf) 
  58.  
  59.               e                          e           rr
  60.         ----------->                --------->   --------->
  61.      (v)            (w)   ====>  (v)          (u)          (w)
  62.         <-----------                <---------   <---------
  63.               r                          er          r
  64.  
  65.      returns edge rr
  66.   */
  67.  
  68.  
  69.   edge r = e->rev;
  70.  
  71.   node v = source(e);
  72.   node w = target(e);
  73.  
  74.   node u = graph::new_node();
  75.  
  76.   copy_node_entry(node_inf);
  77.  
  78.   u->data[0] = node_inf;
  79.  
  80.   e->t = u;
  81.   r->t = u;
  82.  
  83.   edge rr = graph::new_edge(u,w);
  84.   edge er = graph::new_edge(u,v);
  85.  
  86.   FACE(rr) = FACE(e);
  87.   FACE(er) = FACE(r);
  88.  
  89.   r->rev  = rr;
  90.   rr->rev = r;
  91.  
  92.   e->rev  = er;
  93.   er->rev = e;
  94.  
  95.   return rr;
  96.  
  97. }
  98.  
  99.  
  100. edge planar_map::new_edge(edge e1, edge e2, GenPtr face_i)
  101. { 
  102.  /* cout << "NEW_EDGE:\n";
  103.     print_edge(e1); cout << " F = " << int(adj_face(e1)) << "\n";
  104.     print_edge(e2); cout << " F = " << int(adj_face(e2)) << "\n";
  105.     newline;
  106.   */
  107.  
  108.   if (adj_face(e1) != adj_face(e2)) 
  109.     error_handler(1,"planar_map::new_edge: new edge must split a face."); 
  110.  
  111.   face F = adj_face(e1);
  112.   face f = new_face(face_i);
  113.  
  114.   edge y = graph::new_edge(e1,source(e2),before);
  115.   F->head = y;
  116.   FACE(y) = F;
  117.   
  118.   edge x = graph::new_edge(e2,source(e1),before);
  119.   f->head = x;
  120.   FACE(x) = f;
  121.  
  122.   x->rev = y;
  123.   y->rev = x;
  124.  
  125.   for (edge e = succ_face_edge(x); e != x; e = succ_face_edge(e)) 
  126.      FACE(e) = f;
  127.  
  128.   return y;
  129. }
  130.  
  131.  
  132. node planar_map::new_node(const list<edge>& el, GenPtr node_inf)
  133. {
  134.   if (el.length() < 2)
  135.       error_handler(1,"planar_map::new_node(el,i):  el.length() < 2."); 
  136.  
  137.   list_item it = el.first();
  138.  
  139.   edge e0 = el[it];
  140.  
  141.   it = el.succ(it);
  142.  
  143.   face f = adj_face(e0);
  144.  
  145.   edge e;
  146.   forall(e,el)
  147.   { if (adj_face(e) != f)
  148.       error_handler(1,"planar_map::new_node: edges bound different faces."); 
  149.    }
  150.  
  151.   e = el[it];
  152.  
  153.   it = el.succ(it);
  154.  
  155.   GenPtr face_inf = f->inf;
  156.  
  157.   copy_face_entry(face_inf);
  158.   copy_node_entry(node_inf);
  159.  
  160.   edge e1 = split_edge(new_edge(e0,e,face_inf),node_inf);
  161.  
  162.   node u = source(e1);
  163.  
  164.   while(it)
  165.   { copy_face_entry(face_inf);
  166.     e1 = new_edge(e1,el[it],face_inf);
  167.     it = el.succ(it);
  168.    }
  169.  
  170.   return u;
  171. }
  172.  
  173. node planar_map::new_node(face f, GenPtr node_inf)
  174. { return new_node(adj_edges(f),node_inf);
  175.  }
  176.  
  177.  
  178. void planar_map::del_edge(edge x, GenPtr face_i)
  179. {
  180.   edge y  = reverse(x);
  181.   face F1 = adj_face(x);
  182.   face F2 = adj_face(y);
  183.  
  184.   edge e = succ_face_edge(y);
  185.  
  186.   F1->inf = face_i;
  187.  
  188.   if (F1!=F2)
  189.   { edge e = succ_face_edge(y);
  190.     F1->head = e;
  191.     while (e!=y)
  192.     { FACE(e) = F1;
  193.       e = succ_face_edge(e);
  194.      }
  195.  
  196.     del_face(F2);
  197.    }
  198.   else
  199.   { e = succ_face_edge(e);
  200.  
  201.     if (e!=y) // no isolated edge
  202.       F1->head = e;   
  203.     else 
  204.       del_face(F1);
  205.  
  206.    }
  207.  
  208.   graph::del_edge(x);
  209.   graph::del_edge(y);
  210.  
  211. }
  212.  
  213.  
  214. void planar_map::clear() 
  215. { face f;
  216.   forall(f,F_list) 
  217.   { clear_face_entry(f->inf);
  218.     delete f;
  219.    }
  220.   F_list.clear();
  221.   graph::clear();
  222.  }
  223.  
  224. planar_map::planar_map(const graph& G) : graph(G)
  225.  
  226. // input: planar embedded graph represented by a bidirected directed graph G 
  227. // i.e., for each node v of G the adjacent edges are sorted counter-clockwise. 
  228. // computes planar map representation (faces!)
  229. // For each face F the information of one of its edges is copied into F
  230.  
  231. { 
  232.   edge e,e1;
  233.   edge_array<edge> Rev(*this);
  234.  
  235.   if (compute_correspondence(*this,Rev) == false)
  236.      error_handler(999,"planar_map: graph is not bidirected");
  237.  
  238.   if (!PLANAR(*this)) 
  239.      error_handler(1,"planar_map: Graph is not planar."); 
  240.  
  241.  
  242.   forall_edges(e,*this) e->rev = Rev[e];
  243.  
  244.  
  245.   Rev.clear();
  246.  
  247.   // compute faces
  248.  
  249.   edge_array<bool> F(*this,false);
  250.  
  251.   forall_edges(e,*this)
  252.    if (!F[e])
  253.     { F[e] = true;
  254.       face f = new_face(e->data[0]);  // copy entry of first edge into face
  255.       G.copy_edge_entry(f->inf);
  256.       e->data[0] =  f;
  257.       f->head = e;
  258.       e1 = succ_face_edge(e);
  259.       while (e1 != e)
  260.       { e1->data[0] = f;
  261.         F[e1] = true;
  262.         e1 = succ_face_edge(e1);
  263.        }
  264.      } 
  265.  
  266. } 
  267.  
  268.  
  269. list<edge> planar_map::triangulate()
  270. {
  271.   node v,w;
  272.   edge e,e1,e2,e3;
  273.  
  274.   list<edge> L;
  275.  
  276.   node_array<bool> marked(*this,false);
  277.  
  278.   forall_nodes(v,*this)
  279.   {
  280.     list<edge> El = adj_edges(v);
  281.  
  282.     forall(e,El) marked[target(e)] = true;
  283.  
  284.     forall(e,El)
  285.     { 
  286.       e1 = e;
  287.       e2 = succ_face_edge(e1);
  288.       e3 = succ_face_edge(e2);
  289.  
  290.       face F = FACE(e1);
  291.  
  292.       while (target(e3) != v)
  293.       { 
  294.  
  295.         // e1,e2 and e3 are the first three edges in a clockwise 
  296.         // traversal of a face incident to v and t(e3) is not equal
  297.         // to v.
  298.  
  299.         if ( !marked[target(e2)] )
  300.         { 
  301.           // we mark w and add the edge {v,w} inside F, i.e., after
  302.           // dart e1 at v and after dart e3 at w.
  303.  
  304.           marked[target(e2)] = true;
  305.   
  306.           e1 = new_edge(e1,e3,F->inf);
  307.           e2 = e3;
  308.           e3 = succ_face_edge(e2);
  309.  
  310.           L.append(e1);
  311.         }
  312.         else
  313.         { // we add the edge {source(e2),target(e3)} inside F, i.e.,
  314.           // after dart e2 at source(e2) and before dart 
  315.           // reversal_of[e3] at target(e3).
  316.  
  317.           e3 = succ_face_edge(e3); 
  318.  
  319.           e2 = new_edge(e2,e3,F->inf);
  320.  
  321.           L.append(e2);
  322.  
  323.         }
  324.       } //end of while
  325.  
  326.     } //end of stepping through incident faces
  327.  
  328.    forall_adj_nodes(w,v) marked[w] = false;
  329.  
  330.   } // end of stepping through nodes
  331.  
  332.  return L;
  333.  
  334. }
  335.